Sen(Qian)’s Memo

https://ojs.aaai.org/index.php/AAAI/article/view/5848

PU Learningで選択バイアスが生じると、Class Priorの推定もずれてくる。ここでBiasの影響をできるだけ排した、Class Priorの推定をしたのがこの論文である。

この論文では、3つの重要な仮定を置き、その元での手法を開発した。

• データは$\mathbf{x} \in \mathbb{R}^n$であり、ラベル空間は$\{0, +1\}$とする。
• 得られた分布は、ハイパーパラメタ$\alpha$と、2つの分布$f_0, f_1$によって、以下のように合成されたと考える。

• しかし、上の形だと一定に定まらないそうなので、以下のようにする。

この論文で基本にしてるのはAlphaMaxというアルゴリズムであり、nonparametricでclass priorを推測する。考えとしては、最適解の周りは急激に変化しているので、周りのGradientの変化が最も急なところを最適解とするというもの。

具体的には、何かしらの確率などにCalibrationされた$f(\mathbf{x})$に対して、$Pr(f(\mathbf{x})|\alpha)$を複数個の$\alpha$でサンプリングして、そこから曲線にあてはめて？曲がりが最大の変曲点を見つける感じ。

考えている問題設定としては以下のようなもの。

• Unlabeledの分布は$f$であり、これはNegtaiveの確率分布$f_0$とPositiveの確率分布$f_1$を、ある割合$\pi=p(y=+1)$で混合したものである。$f=\pi f_1 + (1 - \pi) f_0$
• Positiveの分布$f_1^\prime$であり、これは真のPositiveの確率分布$f_1$とは違う=Biasedである。

定式化としては、以下のように何かしらの基底$\phi_i$があるとして、$f_1, f_1^\prime$は違う。

ある分布を構成する係数が一意になるように、φ irreducibilityという仮定を導入した。具体的には、Negative$f_0$は、非自明な基底φの合成で合成できないとしているらしい。

そのうえ、各Kernelの基底$\phi_i, \phi_j$の台=supportは重ならないとも仮定。

ようわからん

もし$f_0$はφ irreducibilityを持つ場合、ある分布に対して、係数の組成はユニークらしい。

Biased PU Dataを複数個のUnbiased PU Dataに分解し、そこからAlphaMaxのアルゴリズムを使いたい。最後に分解した各データからの情報を統合したい。

1. データセットを$K$個の集合$B_i$に分割する。これはk-meansなどのクラスタリングアルゴリズムを使う。
   1. この手法では、まずPositive Dataについてk-meansで分割する(シルエット係数というものを最大化するような$K$を選ぶらしい)。
   2. 次にUnlabeledを、すでに計算されたクラスタの中心との距離に基づいて分割する。
2. 各集合$B_i$について、何かしらのSupportがお互いかぶらないKernel基底の分布$\phi_i$に従うとする。
   1. Positiveデータは、Kernel基底の分布$\phi_i$に従って生成されるとする。
      1. $\phi_i$はお互いに台がかぶらないというが、k-meansでクラスタリングしている以上、割り当てられたエリアのデータしか生成しないので、確かに台がかぶらないという前提からクラスタリングという発想はわかる。
   2. Unlabeledデータは、別の分布$\psi_i$に従う。
   3. つまり、各$B_i$は、$\lambda_i^* \phi_i + (1 - \lambda_i^*)\psi_i$の合成分布によってサンプリングされる。
3. $\gamma_i=\lambda_i^* p_i / \alpha^*$、$\zeta_i = (\psi_i - \lambda_i^* \phi_i)/(a-\lambda_i^*)$。
   1. $p_i$は全体の中で占める$B_i$の個数の割合。
   2. なので、$\gamma_i^* p_i$は、全体の中での$\phi_i$に従うものの割合である。
      1. これに従う各分布$\phi_i$で合成すれば、Positiveの推定分布$f_1^*$になる。
   3. $\zeta_i$は$B_i$のUnlabeledのデータで、$\phi_i$に対応しない残りの部分を示す分布。
      1. これに従う各分布$\zeta_i$で合成すれば、Unlabeledの推定分布$f_0^*$になる。
   4. これらで推定すると、以下のようになる。

   

一番求めたい$\alpha^*$の推定は、$\lambda_i^*, p_i$が必要で、k-meansで各クラスタに分ければ、前者はAlphaMaxで推定でき後者もおのずとわかる。そしてついでに$f_1^*, f_0^*$も、データから分布を(パラメトリック、ノンパラメトリック問わず)推定できれば、おのずとわかるかんじ。

アルゴリズムとしてはこんな感じである。